package 数据流中的中位数;

import java.util.Comparator;
import java.util.PriorityQueue;

//题目描述
//如何得到一个数据流中的中位数？
// 如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。
// 如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。
// 我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。
public class Solution
{
    //优先队列
    PriorityQueue<Integer> minHeap =new PriorityQueue<Integer>();
    PriorityQueue<Integer> maxHeap =new PriorityQueue<Integer>(new Comparator<Integer>()
    {
        @Override
        public int compare(Integer o1, Integer o2)
        {
            return o2.compareTo(o1);
        }
    });
    int count=0;
    public void Insert(Integer num)
    {
        //这样就会大顶堆都是存放的小的数
        //小顶堆都是存放的大的数
       if (count%2==0)
       {
           //偶数次
           maxHeap.offer(num);
           minHeap.offer(maxHeap.poll());
       }
       else
       {
           //奇数次
           minHeap.offer(num);
           maxHeap.offer(minHeap.poll());
       }
       count++;
    }

    public Double GetMedian()
    {
        if (count%2==0)
        {
            return new Double(minHeap.peek()+maxHeap.peek())/2;
        }
        else
        {
            return new Double(minHeap.peek());
        }
    }
}
